【剑指Offer I】36. 二叉搜索树与双向链表
题目
输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点,只能调整树中节点指针的指向。
示例
将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表,第一个节点的前驱是最后一个节点,最后一个节点的后继是第一个节点。
下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。
就地完成转换操作。当转化完成以后,树中节点的左指针需要指向前驱,树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。
解答
思路:中序遍历
首先对于二叉搜索树,中序遍历可以获得其递增序列。
其次,双向链表需要有 pre
和 next
指针(在本题中用二叉树的 left
和 right
指针表示)。也就是说遍历到某个节点时,要同时知道它的前驱和后继,这在递归中比较麻烦。可以换个思路,在遍历到当前节点时,我们知道它的前驱,也知道前驱的后继是当前节点,可以把这两个指针建立起来。
错开建立当前节点的前驱和后继关系:先建立节点的前驱关系,然后节点成为新的前驱,遍历到它的后继节点时,再建立后继关系。
最后,单独处理头尾节点,因为要形成循环链表,还要将头节点的前驱指向尾节点,尾节点的前驱指向头节点。
代码
1 |
|
复杂度
- 时间复杂度
O(N)
:访问树的所有节点。 - 空间复杂度
O(N)
:系统栈空间。
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 namespace LANG!
评论